package offer;

/**
 * 剑指 Offer 13. 机器人的运动范围
 */
public class RangeOfMotion {
    /***
     * 
     * @param m 行
     * @param n 列
     * @param k 目标和
     * @return
     */
    public int movingCount(int m, int n, int k) {

        if (k == 0) {
            return 1; // 只有坐标0,0
        }
        // 可达性记录数组
        boolean[][] vis = new boolean[m][n];
        // 初始化
        vis[0][0] = true;
        int ans = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 首位或者不合法就跳过(默认false)
                if (i == 0 && j == 0 || !isLegal(i, j, k)) {
                    continue;
                }
                // 上方能否连通
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                // 左方能否连通
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                // 记录结果
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }

    // 合法性判断
    public boolean isLegal(int x, int y, int k) {
        return digitalSum(x) + digitalSum(y) <= k;
    }

    // 位数和
    public int digitalSum(int number) {
        if (number < 10) {
            return number;
        }
        // m and n <= 100, m - 1、 n - 1 <= 99;
        int sum = number / 10 + number % 10;
        return sum;
    }
}
